Back to Home

Leetcode Day 1

@2025-04-28,今天开始开新坑,刷刷Leetcode,虽然我是学数学的,但是代码太菜不太好找饭吃可能@

Leetcode 12

  • 1 <= num <= 3999,输入的 int 换成级数表示,然后对 4 和 9 的情况做一下处理,可以吗?

Pasted image 20250428213451.png

这个题目好像已经把程序给出来了。Pasted image 20250428214025.png

那就先看是不是 4 或者 9,然后判断是哪一种,然后剪掉,然后

class Solution:
    def intToRoman(self, num: int) -> str:
	   first_int = num % 10
	   if first_int == 4:
		   pass
	   elif first_int == 9:
		   pass
	   else:
	   

写到这觉得好像写成级数更好处理,因为判断减法要写太多 if 了。

class Solution:
	def expandToSeries(self, num: int) -> list:
		# Assume we have a * 1000 + b * 100 + c * 10 + d * 1
		a = num % 1000
		b = (num - a * 1000) % 100
		c = ...
    def intToRoman(self, num: int) -> str:
	    
太蠢了

直接转换成字符串。可以用列表推导式,此外,为什么不用一个table?

列表表达式 [expression for item in iterable if condition]
class Solution:
	def intToRoman(self, num: int) -> str:
		thousands = ["", "M", "MM", "MMM"] 
		hundreds = ["", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"] 
		tens = ["", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"] 
		ones = ["", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"]
		num_list = [int(char) for char in str(num)]
		
		result = thousands[num_list[0]] + hundreds[num_list[1]] + tens[num_list[2]] + ones[num_list[3]]
		return result
		
太蠢了,这样不是假设一定有四位了吗
a = num // 1000
b = (num % 1000) // 100
c = (num % 100) // 10
d = num % 10

result = thousands[a] + hundreds[b] + tens[c] + ones[d]

AI:使用贪心算法

def int_to_roman_greedy(num: int) -> str:
    # 值和符号的映射,必须从大到小排列
    value_symbols = [
        (1000, "M"), (900, "CM"), (500, "D"), (400, "CD"), (100, "C"),
        (90, "XC"), (50, "L"), (40, "XL"), (10, "X"), (9, "IX"),
        (5, "V"), (4, "IV"), (1, "I")
    ]

    roman_numeral = []
    for value, symbol in value_symbols:
        while num >= value:
            roman_numeral.append(symbol)
            num -= value
        if num == 0: # 提前结束
            break
    return "".join(roman_numeral)

# 示例
print(f"1994 -> {int_to_roman_greedy(1994)}") # MCMXCIV
print(f"58 -> {int_to_roman_greedy(58)}")   # LVIII
print(f"3 -> {int_to_roman_greedy(3)}")     # III

Pasted image 20250428221907.png

通过

  • 之后来学
Warning

55

如果在某一步的数比距离大,那么结束。

感觉正着走完全就是穷举了,没有什么简化办法。

不,好像有,如果紧接着的下一位位数不变,那么跳到下一位肯定没问题。

当前位数 ,步数 ,考虑 的步数 ,如果 ,那么跳到这里没有问题。

对于 有问题的情况下,跳 ,类推。

代码实现

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        position = 0
        j = 0
        if nums[position] == 0:
            return False
        while j <= nums[position]:
            if position + nums[position] < len(nums):
                return True
            elif nums[position + j] >= nums[position] - j:
                position = position + j
                j = 1
            else:
                j += 1

Pasted image 20250428231700.png

if position + nums[position] < len(nums): 这一句写反号了

提交:Pasted image 20250428231914.png
再次修改

Pasted image 20250428232120.png

Pasted image 20250428232125.png
看出你最后懒了,判断太草率了。好好想想什么时候截止:

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        n = len(nums)
        if n == 1:
            return True    
        position = 0
        j = 0
        if nums[position] == 0:
            return False
        while j <= nums[position]:
            if position + nums[position] >= len(nums) - 1:
                return True
            elif nums[position + j] >= nums[position] - j:
                position = position + j
                j = 1
            else:
                j += 1
        return position == n + 1

还捉了个虫Pasted image 20250428232403.png

Pasted image 20250428232518.pngPasted image 20250428232520.png

AI 教学

class Solution: # 最终简洁版
    def canJump(self, nums: List[int]) -> bool:
        n = len(nums)
        max_reach = 0
        for i in range(n):
            if i > max_reach:
                return False
            max_reach = max(max_reach, i + nums[i])
            # 优化:如果已经可以覆盖终点,没必要继续遍历
            # if max_reach >= n - 1:
            #     return True
        # 如果循环正常结束,说明最后一个位置 n-1 也是可达的 (i <= max_reach)
        return True

哎,薄纱。